﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Alogrithms
{
    public class QuickFindUF
    {
        private int[] id;
        private int m_count;

        // instantiate N isolated components 0 through N-1
        public QuickFindUF(int N)
        {
            m_count = N;
            id = new int[N];
            for (int i = 0; i < N; i++)
                id[i] = i;
        }

        // return number of connected components
        public int count()
        {
            return m_count;
        }

        // Return component identifier for component containing p
        public int find(int p)
        {
            return id[p];
        }

        // are elements p and q in the same component?
        public bool connected(int p, int q)
        {
            return id[p] == id[q];
        }

        // merge components containing p and q
        public void union(int p, int q)
        {
            if (connected(p, q)) return;
            int pid = id[p];
            for (int i = 0; i < id.Length; i++)
                if (id[i] == pid) id[i] = id[q];
            m_count--;
        }

        public override string ToString()
        {
            return string.Join(" ", id);
        }

        public string Run()
        {
            union(9, 6);
            union(2, 5);
            union(3, 9);
            union(6, 0);
            union(5, 9);
            union(7, 2);
            return ToString();
        }
    }


}
